package day003;

import java.util.LinkedList;
import java.util.Stack;

public class Code02_IsBST {

    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value){
            this.value = value;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    // 中序遍历存入数组，再判断是否增序
    public static boolean isBST(Node head){
        LinkedList<Integer> a = new LinkedList<>();
        process(head, a);
        System.out.println(a.toString());
        for(int i = 1; i < a.size(); i++){
            if(a.get(i) < a.get(i-1)){
                return false;
            }
        }
        return true;
    }

    public static void process(Node head, LinkedList<Integer> a){
        if(head == null){
            return;
        }

        process(head.left, a);
        a.add(head.value);
        process(head.right, a);
    }
    // 方法二 需要借助一个全局变量存储前一个值
    public static int preValue = Integer.MIN_VALUE;
    public static boolean isBST2(Node head){
        if (head == null){
            return true;
        }

        boolean isLeftBst = isBST2(head.left);
        if(!isLeftBst){
            return false;
        }
        if(head.value > preValue){
            preValue = head.value;
        }else{
            return false;
        }
        boolean isRightBst = isBST2(head.right);
        return isRightBst;
    }

    //
    public static boolean isBST3(Node head){
        if(head == null){
            return true;
        }
        Stack<Node> stack = new Stack<>();
        while(!stack.isEmpty() || head != null){
            if(head != null){
                stack.push(head);
                head = head.left;
            }else{
                head = stack.pop();
                if(head.value <= preValue){
                    return false;
                }else{
                    preValue = head.value;
                }

                head = head.right;
            }
        }
        return true;
    }

    // 树形动态规划
    public static boolean isBST4(Node head){
        if(head == null){
            return true;
        }
        ReturnData res = process2(head);
        return res.isBS;
    }

    public static class ReturnData{
        public boolean isBS;
        public int min;
        public int max;

        public ReturnData(boolean isBS, int min, int max) {
            this.isBS = isBS;
            this.min = min;
            this.max = max;
        }
    }

    public static ReturnData process2(Node head){
        if (head == null){
            return null;
        }
        ReturnData lData = process2(head.left);
        ReturnData rData = process2(head.right);

        int min = head.value;
        int max = head.value;
        boolean isBS = true;
        if(lData != null){
            min = Math.min(head.value, lData.min);
            max = Math.max(head.value, lData.max);
        }
        if(rData != null){
            min = Math.min(head.value, rData.min);
            max = Math.max(head.value, rData.max);
        }

        if(lData != null && (!lData.isBS || lData.min >= head.value)){
            isBS = false;
        }
        if(rData != null && (!rData.isBS || rData.max <= head.value)){
            isBS = false;
        }



//        if(lData == null && rData != null){
//            min = Math.min(head.value, rData.min);
//            //max = Math.max(head.value, rData.max);
//            if(head.value >= rData.min || !rData.isBS){
//                isBS = false;
//            }
//        }
//        if(lData != null && rData == null){
//            //min = Math.min(head.value, lData.min);
//            max = Math.max(head.value, lData.max);
//            if(head.value <= lData.max || !lData.isBS){
//                isBS = false;
//            }
//        }
//        if(lData != null && rData != null){
//            min = Math.min(head.value, rData.min);
//            max = Math.max(head.value, rData.max);
//            if(head.value >= rData.min || head.value <= lData.max || !lData.isBS || !rData.isBS){
//                isBS = false;
//            }
//        }


        return new ReturnData(isBS, min,max);


    }

    public static void main(String[] args) {
        Node n16 = new Node(16);
        Node n17 = new Node(17, n16, null);
        Node n15 = new Node(15,null, n17);
        Node n19 = new Node(19);
        Node n18 = new Node(18, n15, n19);
        Node n2 = new Node(2);
        Node n9 = new Node(9);
        Node n5 = new Node(5, n2, n9);
        Node n12 = new Node(12, n5, n18);

        System.out.println(isBST4(n12));
    }
}
























